Multi-Protocol Label Switching (MPLS) is a data-carrying mechanism and protocol for packet-switched networks, such as Internet Protocol (IP) networks. MPLS encapsulates IP packets and attaches an MPLS header including a label stack. MPLS-labeled packets are routed through a network along logical Label Switched Paths (LSPs) by performing a Label Lookup/Switch at routing nodes instead of a lookup into the IP table. An LSP is a logical entity that defines a unidirectional traffic flow between two network endpoints, and may include numerous other attributes, such as bandwidth requirements, one or more explicit routes, and the like. When an LSP does not include an explicit route, the actual route of traffic between the endpoints is determined dynamically by Label Switching Routers. Many independent LSPs may be routed through a single network node or link. MPLS supports multiple service models, and provides advantageous traffic management tools.
Fast Reroute (FRR)—also known in the art as MPLS local protection—is a network resiliency mechanism that protects network facilities, such as links and nodes, by defining one or more bypass or backup LSPs to carry traffic around each facility (parallel bypass LSPs protecting the same facility are called a bypass bundle). In the event of a network failure, traffic is directed onto a backup LSP beginning at a Point of Local Repair (PLR), bypassing the failure and merging with the primary LSP at a Merge Point (MP). FRR provides faster recovery than, e.g., recovery mechanisms at the IP layer (which may take several seconds), because the decision of recovery is strictly local. FRR targets to reroute traffic within 50 ms upon failure.
FRR relies on the RSVP traffic engineering (RSVP-TE) protocol, whereby each LSP traversing a link reserves sufficient bandwidth, or link capacity, for its traffic. Link bandwidth not reserved for primary LSPs, referred to herein as spare link capacity or protection bandwidth, is available for FRR and allows bypass LSPs to be routed along the link. Defining bypass LSPs along links having sufficient spare link capacity to carry the traffic of a protected facility, while complying with numerous system constraints to minimize the impact of a failure on MPLS operation, stands as the central problem in FRR design and implementation.
The design of FRR bypass LSPs using an arc-flow formulation is known in the art. In an arc-flow formulation, each link, or network arc, is assigned a decision variable having a binary, integer value (i.e., 0 or 1) indicating whether it is included in a bypass LSP or not. The arc-flow formulation first finds the spare link capacity using a mixed integer linear programming (MILP) model, and then derives routes for the bypass LSPs based on the discovered spare link capacity. This process is computationally complex, and is limited in its ability to accommodate other network constraints in formulating the bypass LSPs.